package practice;

class onezerobag1 {
/*
* 其中N表示的是N个物品，V表示的是最大载重量
* weight[]表示的物品的重量数组
* value[]表示的是物品的价值数组
* */
    public static void Pack(int []weights,int []value,int N,int V)
    {
//       使用动态规划的方式求解
//        1.定义dp[i][j]表示前i物品放入容量为j的背包可以获得的最大价值
//        2.递推公式：
//         如果不装第i个物品：dp[i][j]=dp[i-1][j]
//         如果装第i个物品，dp[i][j]=dp[i-1][j-weight[i]]+value[i];
//        3.初始条件是：如果什么都不拿也就是i=0的时候价值肯定为0,容量为0价值也wei0
        int [][]dp = new int[N+1][V+1];

        for (int i = 0; i <=N; i++) {
            dp[i][0]=0;
        }
        for (int i = 0; i <=V ; i++) {
            dp[0][i]=0;
        }
        for (int i = 1; i <=N ; i++) {
            for (int j = 0; j <=V ; j++) {
                if(j>=weights[i])
                {
                    dp[i][j]=Math.max(dp[i-1][j],dp[i-1][j-weights[i]]+value[i]);
                }else
                {
                    dp[i][j]=dp[i-1][j];
                }
            }
        }
//        如果是要取得最大价值的话就可以直接输出了，如果想的没错的话应该是dp[N][V]
        System.out.println(dp[N][V]);


    }


}
//现在开始改装，就是正常计算机从0开始的
//1.定义dp[i][j]为前i个物品，容量为j获得的最大价值
//2.定义递推公式：
//当不取第i个物品，也就是不取下标为i-1这个物品的时候 :dp[i][j] =dp[i-1][j]
//当取第i个物品的时候dp[i][j] = dp[i-1][j-weight[i-1]]+value[i-1];
class onezeropack2{
    public static void Pack1(int []weights,int []value,int N,int V)
    {
        int [][]dp = new int[N+1][V+1];
        for (int i = 0; i <=N ; i++) {
            dp[i][0]=0;
        }
        for (int i = 0; i <=V ; i++) {
            dp[0][i]=0;
        }
        for (int i = 1; i <=N; i++) {
            for (int j = 0; j <=V ; j++) {
                if(j>=weights[i-1])//这个地方写错了最开始，他应该是
                {
                    dp[i][j]=Math.max(dp[i-1][j],dp[i-1][j-weights[i-1]]+value[i-1]);
                }else
                    dp[i][j] = dp[i-1][j];
            }
        }
        System.out.println(dp[N][V]);
    }
    public static void main(String[] args) {
//    如果使用上面的递推公式的话这里有一个前置条件：第0个物品的质量和价值都是0.
        int []weights = { 2 ,3 ,4 ,5 };
        int []value = {3 ,4 ,5 ,7 };
        int N = 4,V=9;
        Pack1(weights,value,N,V);

    }
}
